package test;

//单词搜索：https://leetcode.cn/problems/word-search/
public class Exist {
	int m,n;
    boolean[][] check;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    //dfs: 以[i,j]位置为起点，能否拼成word
    public boolean dfs(char[][] board,int i,int j,String word,int pos){
        //如果pos==word.length，说明正好能拼成，返回true
        if(pos==word.length()){
            return true;
        }
        //上下左右帅哥方向尝试
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            //保证不越界
            if(x<m&&y<n&&x>=0&&y>=0){
                if(check[x][y]==false&&board[x][y]==word.charAt(pos)){
                    //标记位置，表面该位置使用过了
                    check[x][y]=true;
                    //只要后面位置能符合就好返回true，而当前位置也为true，因此直接返回true
                    if(dfs(board,x,y,word,pos+1)==true)
                        return true;
                    //走到该位置，说明后面的位置无法拼成word
                    check[x][y]=false;
                }
            }
        }
        //如果能拼成，则会因为前面的语句一直返回true，到这，说明每个所有位置都枚举失败了，因此返回true
        return false;
    }

    //主函数： 遍历每个位置，寻找可以作为word首个字母的位置
    public boolean exist(char[][] board, String word) {
        m=board.length;
        n=board[0].length;
        check=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==word.charAt(0)){
                    check[i][j]=true;
                    //判断以[i,j]位置为起点是否能构成字符串word
                    boolean ret=dfs(board,i,j,word,1);
                    if(ret==true){
                        return true;
                    }
                    check[i][j]=false;
                }
            }
        }
        return false;
    }
}
